import tool.TreeNode;
import tool.TreeNodePrint;
import tool.input;

import java.util.Deque;

/**
 * @Description: 二叉搜索树中的搜索
 * 给定二叉搜索树（BST）的根节点 root 和一个整数值 val。
 * 你需要在 BST 中找到节点值等于 val 的节点。
 * 返回以该节点为根的子树。 如果节点不存在，则返回 null 。
 *
 * @Date:Create in 20:30  2022/8/2
 */
public class searchBST0700 {
    public static void main(String[] args) {
        String s1 = "[4,2,7,1,3]";
        int val = 2;
        TreeNode root1 = input.getTree(s1);
        TreeNodePrint.printTree(root1);
        TreeNode root3 = searchBST(root1, val);
        TreeNodePrint.printTree(root3);
    }

    public static TreeNode searchBST(TreeNode root, int val) {
        return Dfs(root,val);
    }
    public static TreeNode Dfs(TreeNode root, int val){
         if(root==null) return null;
         if(root.val==val) return root;
         TreeNode left = Dfs(root.left,val);
         TreeNode right = Dfs(root.right,val);
         if(left!=null) return left;
         else return right;
    }
}
